package _05_二叉树;

public class _99_恢复二叉搜索树 {

    private TreeNode prev;

    private TreeNode first;

    private TreeNode second;

    // 由于需要恢复二叉搜索树，其中序遍历一定会产生逆序对，所以只需要遍历二叉树，找出逆序对，交换他们的位置即可
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    // morris遍历二叉树
    // 时间复杂度O(N)，空间复杂度O(1)
    public void inorder(TreeNode node) {
        while (node != null) {
            if (node.left != null) {
                // 寻找node的前驱节点
                TreeNode pre = node.left;
                while (pre.right != null && pre.right != node) {
                    pre = pre.right;
                }
                // 查看前驱节点
                if (pre.right == null) {
                    // 前驱节点指向当前节点
                    pre.right = node;
                    node = node.left;
                } else {
                    // 不能提前结束，需要恢复指针指向
                    set(node);
                    pre.right = null;
                    node = node.right;
                }
            } else {
                // 直接遍历节点
                set(node);
                // 下一个节点为后继节点，也就是上面改变索引的位置
                node = node.right;
            }
        }

    }


    // 由于需要恢复二叉搜索树，其中序遍历一定会产生逆序对，所以只需要遍历二叉树，找出逆序对，交换他们的位置即可
    public void recoverTree1(TreeNode root) {
        inorder1(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    public void inorder1(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        if (!set(node)) return;
        inorder(node.right);
    }

    public boolean set(TreeNode node) {
        // 比较值大小
        if (prev != null && prev.val > node.val) {
            second = node;
            if (first != null) return false;
            first = prev;
        }
        prev = node;
        return true;
    }
}
